﻿namespace Leetcode.N1563;
public class Solution
{
    public int StoneGameV(int[] stoneValue)
    {
        var sums = new int[stoneValue.Length + 1];
        for (int i = 1; i < sums.Length; i++)
        {
            sums[i] = sums[i - 1] + stoneValue[i - 1];
        }
        var n = stoneValue.Length;
        var ans = new int[n][];
        ans[0] = new int[n];

        for (int count = 1; count < n; count++)
        {
            ans[count] = new int[n];
            for (int i = 0; i < n - count; i++)
            {
                var maxTotal = 0;
                for (int leftCount = 0; leftCount < count; leftCount++)
                {
                    var leftSum = sums[i + leftCount + 1] - sums[i];
                    var rightSum = sums[i + count + 1] - sums[i + leftCount + 1];
                    var total = 0;
                    if (leftSum < rightSum)
                    {
                        total = leftSum + ans[leftCount][i];
                    }
                    else if (leftSum == rightSum)
                    {
                        var leftTotal = leftSum + ans[leftCount][i];
                        var rightTotal = rightSum + ans[count - (leftCount + 1)][i + leftCount + 1];
                        total = Math.Max(leftTotal, rightTotal);
                    }
                    else
                    {
                        total = rightSum + ans[count - (leftCount + 1)][i + leftCount + 1];
                    }
                    maxTotal = Math.Max(maxTotal, total);
                }
                ans[count][i] = maxTotal;
            }
        }
        return ans[n - 1][0];
    }
}
